import collections
from typing import List


class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        start = (-1, -1)
        end = set()
        visited = set()

        for i in range(m):
            for j in range(n):
                if grid[i][j] == "*":
                    start = (i, j)
                if grid[i][j] == "#":
                    end.add((i, j))
                if grid[i][j] == "X":
                    visited.add((i, j))

        ans = 0
        queue = collections.deque([start])
        while queue:
            for _ in range(len(queue)):
                i1, j1 = queue.popleft()
                if (i1, j1) in end:
                    return ans
                for (i2, j2) in neighbors(i1, j1):
                    if (i2, j2) not in visited:
                        visited.add((i2, j2))
                        queue.append((i2, j2))
            ans += 1
        return -1


if __name__ == "__main__":
    # 3
    print(Solution().getFood(grid=[["X", "X", "X", "X", "X", "X"],
                                   ["X", "*", "O", "O", "O", "X"],
                                   ["X", "O", "O", "#", "O", "X"],
                                   ["X", "X", "X", "X", "X", "X"]]))

    # -1
    print(Solution().getFood(grid=[["X", "X", "X", "X", "X"],
                                   ["X", "*", "X", "O", "X"],
                                   ["X", "O", "X", "#", "X"],
                                   ["X", "X", "X", "X", "X"]]))

    # 6
    print(Solution().getFood(grid=[["X", "X", "X", "X", "X", "X", "X", "X"],
                                   ["X", "*", "O", "X", "O", "#", "O", "X"],
                                   ["X", "O", "O", "X", "O", "O", "X", "X"],
                                   ["X", "O", "O", "O", "O", "#", "O", "X"],
                                   ["X", "X", "X", "X", "X", "X", "X", "X"]]))

    # 2
    print(Solution().getFood(grid=[["O", "*"],
                                   ["#", "O"]]))

    # -1
    print(Solution().getFood(grid=[["X", "*"],
                                   ["#", "X"]]))

    # 2
    print(Solution().getFood(grid=[["O", "O", "O", "#", "X"],
                                   ["O", "X", "O", "O", "*"],
                                   ["O", "X", "#", "X", "O"],
                                   ["#", "O", "O", "X", "O"],
                                   ["O", "X", "O", "O", "O"]]))
